package graph.coloring;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 图的dfs  bfs   染色法  并查集判定
 */
public class 判断二分图_785 {
            public boolean isBipartite_dfs(int[][] graph) {
                // 0表示点未访问  1和-1表示两种颜色
                int[] visited = new int[graph.length];
                for(int i = 0; i < graph.length; i++) {
                    // 依据题意 可能不是联通图 因此需要每个都来染色
                    // 不连通的孤岛直接染色成1即可 如果能够在这个连通子分量里面成功染色  也是可以分的
                    if(visited[i] == 0 && dfs(graph, visited, i, 1)) {
                        return  false;
                    }
                }
                return true;
            }

            private boolean dfs(int[][] graph, int[] visited, int i, int color) {
                if(visited[i] != 0) {  // 本子连通图内部之前访问过该节点
                    //  节点 A自身是 -1 相邻节点B应该染色成-1  但是之前是1 说明AB同色  一条边的相邻节点只能放到一个集合里
                    // 返回true  表示有异常
                    return visited[i] != color;
                }
                // 未染色过
                visited[i] = color;
                for(int t : graph[i]) { // 对该节点的连通节点  染上相反的颜色  如果任何一个之前染色过且颜色相同
                    if(dfs(graph, visited, t, -color)) {
                        return true;
                    }
                }
                return false;
            }



            public boolean isBipartite_bfs(int[][] graph) {
                int[] visited = new int[graph.length]; // 0表示点未访问  1和-1表示两种颜色
                Queue<Integer> queue = new LinkedList<>();
                for (int i = 0; i < graph.length; i++) {
                    if(visited[i] != 0) continue;
                    queue.offer(i);  visited[i] = 1; // 第一个节点染色
                    // 对每个节点 取得其邻居
                    // 如果没颜色就染色并塞进来 下一轮判断其相邻点
                    // 如果有颜色判断是否颜色不对  如果不对就返回异常
                    while (!queue.isEmpty()) {
                        Integer node = queue.poll();
                        int color = visited[node];
                        int neighborColor = - color;

                        for (int neighbor : graph[node]) {
                            int neighborCurColor = visited[neighbor];
                            if(neighborCurColor == 0) {
                                visited[neighbor] = neighborColor;
                                queue.offer(neighbor);
                            } else {
                                if(neighborCurColor != neighborColor) {
                                    return false;
                                }
                            }
                        }

                  

            }
        }
        return true;
    }


    public boolean isBipartite_unionFind(int[][] graph) {
        UnionFind uf = new UnionFind(graph.length);
        // 遍历每个顶点  判断是否之前就已经将该点合并到了其邻接点集中  说明这个点无法和邻接点集分开成两个集合
        for (int i = 0; i < graph.length; i++) {
            for (int j : graph[i]) {
                if(uf.isConnected( i, j)) return false;
                uf.union(graph[i][0], j);  // 临接点合并为同一个根  这些点组成一个集合
            }
        }
        return true;
    }
    
            class UnionFind {
        int[] uf;
        public UnionFind(int size) {
            uf = new int[size];
            for(int i = 0; i< size; i++) {
                uf[i] = i; // 每个点的根默认初始化为自身
            }
        }

        /**
                  * 把一个节点的根赋值给另一个节点的根
                  * @param p 
                  * @param q
                  */
        public void union(int p, int q) {
            uf[find(p)] = find(q);
        }
        
        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }

        /**
                  * 查找一个节点的根
                  * @param p
                  */
        private int find(int p) {
            if(uf[p] == p) return p;
            return uf[p] = find(uf[p]); // 不等就递归find自身的root 并把等的root返回回去赋值给 uf[p]
        }
    }
}
